package jianzhiOffer;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * TODO
 *
 * @author 司松坡
 * @createTime 2023年05月18日
 */
public class Jian59 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        int max = nums[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        //初始堆
        for (int i = 0; i < k; i++) {
            max = Math.max(max, nums[i]);
            deque.push(nums[i]);
        }
        res[0] = max;
        if (nums.length == 1){
            return res;
        }
        int sit = 1;
        for (int i = k; i < nums.length; i++) {
            int integer = deque.removeLast();
            deque.push(nums[i]);
            if (nums[i] > max) {
                res[sit] = nums[i];
                max = nums[i];
            } else if (max == integer) {
                max = Integer.MIN_VALUE;
                for (int l : deque) {
                    max = Math.max(max, l);
                }
                res[sit] = max;
            } else {
                res[sit] = max;
            }
            sit += 1;
        }
        return res;
    }

    @Test
    public void test(){
        System.out.println("maxSlidingWindow(new int[]{1,3,1,2,0,5},3) = " + Arrays.toString(Arrays.stream(maxSlidingWindow(new int[]{1, 3, 1, 2, 0, 5}, 3)).toArray()));
    }

}
